지금까지의 복잡한 승패 전파와 가지치기 알고리즘을 통해, 우리는 마침내 더 이상 단순화할 수 없는 '루트 음절'들로 구성된 그래프만을 남겼습니다. 하지만 이 루트 음절들도 모두 동등한 중요도를 갖는 것은 아닙니다.
예를 들어 '캉'은 루트 음절이지만, '캉'으로 시작하는 단어는 '캉캉', '캉딩' 뿐이고 '캉'으로 끝나는 단어는 거의 없습니다. 게임 초반에 누군가 의도적으로 사용하지 않는 한, 게임 중에 '캉'이라는 글자를 만날 일은 전혀 없습니다.
반면 '균'과 같은 음절은 '균'으로 시작하는 단어와 끝나는 단어가 모두 풍부하여 다른 수많은 단어와 복잡하게 얽혀있습니다. 따라서 '균'은 게임의 흐름에 자주 등장하며, 승패를 가르는 핵심적인 분석 대상이 됩니다.
이러한 음절의 '중요도'와 '연결성'의 차이를 체계적으로 분석하기 위해, 우리는 강한 연결 요소(Strongly Connected Component, SCC)라는 그래프 이론의 개념에 주목해야 합니다.
조금 기술적인 개념이지만, SCC를 도시의 '지역구'에 비유하면 쉽게 이해할 수 있습니다.
강한 연결 요소(SCC)란, 그래프 내에서 서로에게 도달할 수 있는 정점들의 집합을 의미합니다. 즉, 하나의 SCC(지역구) 안에 속한 어떤 음절에서든, 몇 개의 단어를 거쳐 그 지역구 안의 다른 모든 음절로 이동하는 것이 가능합니다. 이 지역구 안에서는 자유로운 양방향 통행이 가능한 셈이죠.
그래프 전체를 SCC 단위로 묶어서 보면, 마치 여러 개의 지역구들이 일방통행 고속도로로 연결된 모습이 됩니다. 한 지역구(SCC)에서 다른 지역구로 일단 넘어가면, 다시는 이전 지역구로 돌아올 수 없는 비가역성(Irreversibility)을 갖게 되죠.
이러한 SCC의 특성은 끝말잇기 게임의 흐름과 전략에 중요한 시사점을 줍니다.
게임의 흐름과 중요도: 게임은 항상 선행 SCC에서 후행 SCC로, 즉 일방통행 도로를 따라 흘러갑니다. 한번 후행 SCC, 즉 '도심'으로 진입하면 다시는 선행 SCC인 '외곽'으로 빠져나갈 수 없습니다. 따라서 가장 마지막에 위치한, 더 이상 다른 곳으로 갈 수 없는 종착지 SCC에 속한 음절들이 게임의 핵심 무대가 되며 등장 빈도가 매우 높아집니다.
분석의 순서: 어떤 음절의 승패는 자신보다 뒤에 있는, 즉 후행 SCC의 승패에만 영향을 받습니다. 따라서 루트 음절 전체를 분석할 때는, 가장 마지막 종착지 SCC부터 승패를 분석하고 그 결과를 앞선 SCC에 역으로 전파시키는 방식이 합리적입니다.
실제 국어사전 데이터를 기반으로 루트 음절 그래프를 분석해 보면, 매우 흥미로운 구조가 나타납니다. 바로 거대한 종착지 SCC 한 개와, 그곳으로 향하는 수많은 작은 선행 SCC들로 구성되어 있다는 점입니다.
마치 하나의 거대한 '메트로폴리스'와, 그곳으로 들어오는 수많은 '위성도시'나 '진입로' 같은 모습이죠. 이 구조에 기반하여, 우리는 루트 음절을 두 종류로 분류합니다.
이러한 이유로, 끝말잇기를 깊이 있게 연구하거나 고수들의 대결을 분석할 때는 대부분 '주요 루트 음절'의 관계와 그 안에서의 승패 여부에 초점을 맞추게 됩니다.